The present invention relates to a Viterbi decoder and, more specifically, to a processor implementation of a Viterbi decoder with a processor.
Wireless communication is an ever advancing field in which data is transmitted from source to destination through a wireless medium. Typically, the data is transmitted as data packets using various protocols such as IEEE 802.11, IEEE 802.16, Global System for Mobile (GSM), and Code Division Multiple Access (CDMA). Data packets transmitted wirelessly are prone to noise, which can either cause some packets to be lost or corrupted. Such lost data packets cannot be recovered and have to be retransmitted to the destination. On the other hand, corrupted data packets can be recovered using various Forward Error Correction (FEC) codes. Some commonly used FEC codes are convolution codes, Reed-Solomon code, BCH code, etc. Of the above mentioned FEC codes, convolution codes are the most commonly used. Prior to the transmission, the data packets are convolutionally encoded by a convolution encoder. At the destination, the data packets are decoded using a Viterbi decoder.
A Viterbi decoder is a maximum likelihood decoder that receives a convolutionally encoded data stream from a data source. After reception of a convolutionally encoded data stream, the Viterbi decoder predicts state of the convolution encoder based on the received convolutionally encoded data stream. For that, the Viterbi decoder maintains a register for storing a plurality of bits representing the state of the convolution encoder. For example, if the convolutionally encoded data stream was generated by a convolution encoder having constraint length ‘K’, then the Viterbi decoder would use ‘K−1’ bits to represent the state of the convolution encoder. Thus, there can be 2k−1 expected states of the convolution encoder. Hereinafter, 2k−1 expected states is referred to as a first set of states. Each state in this first set of states has an associated path metric value. Based on the convolutionally encoded data stream, the Viterbi decoder predicts a second set of states. The second set of states is the next expected state of the first set of states. For each state in the second set of states the Viterbi decoder calculates a new path metric value based on the path metric value associated with the first set of states. Consequently, the Viterbi decoder calculates a set of decision bits based on the new path metric values. The set of decision bits is stored in a trace back register, and the new path metric values are stored in a memory buffer.
Subsequent to generation of the set of decision bits, the Viterbi decoder operates in a trace back mode. In the trace back mode the Viterbi decoder selects a state having the best path metric value from the second set of states. Thereafter, the Viterbi decoder extracts a decision bit from the trace back register based on the selected state. The extracted decision bit is the decoded data bit.
Thus, the Viterbi decoder predicts the second set of states. Each state in the second set of states has an associated path metric value. Thus, a processor that is configured to implement the Viterbi decoder has to perform multiple data move operations to retrieve the path metric values and the set of decision bits from the memory buffer and the trace back register respectively. Such data move operations may consume many processor clock cycles and thus may slow down the overall decoding process.
Thus, there is a need for a Viterbi decoder that is more efficient and uses less processor clock cycles to decode the convolutionally encoded data stream.